// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package sync

import (
	"sync/atomic"
	"unsafe"
)

// poolDequeue是一个无锁固定大小的单生产者，
// 多消费者队列。单个生产商可以从头部推动和弹出
// 而消费者可以从尾部弹出。
// 
// 它增加了一个特性，即它可以将未使用的插槽归零，以避免不必要的对象保留。这对于sync.Pool、
// 很重要，但通常不是文献中考虑的属性。
type poolDequeue struct {
	// headTail将32位头索引和32位
	// 尾索引组合在一起。两者都是VAL模长度（VAL）-1的索引。
	// 
	// tail=队列中最旧数据的索引
	// head=要填充的下一个插槽的索引
	// 
	// 范围内的插槽[tail，head]归消费者所有。
	// 消费者继续拥有此范围之外的插槽，直到
	// 该插槽为零，此时所有权转移给
	// 生产者。
	// 
	// head索引存储在最高有效位，因此
	// 第至少，我们可以自动添加到它，溢出是无害的。
	headTail uint64

	// VAL是存储在这个
	// dequeue中的接口{}值的环形缓冲区。它的大小必须是2的幂。
	// 
	// VAL[i]如果插槽为空且非零，则.typ为零。否则，插槽仍在使用中，直到*both*尾部
	// 索引移到它之外，并且typ已设置为零。此
	// 由使用者原子地设置为零，并由生产者原子地读取
	// 退出队列。
	vals []eface
}

type eface struct {
	typ, val unsafe.Pointer
}

const dequeueBits = 32

// 退出队列Limit是池出列的最大大小。
// 
// 这必须最多（1<<dequeueBits）/2因为检测完整性
// 依赖于环绕环形缓冲区，而不环绕索引
// 我们除以4，因此这适合于32位的整数。
const dequeueLimit = (1 << dequeueBits) / 4

// 在poolDequeue中使用dequeueNil表示接口{}（nil）.
// 由于我们使用nil表示空插槽，因此需要一个哨兵值
// 来表示nil.
type dequeueNil *struct{}

func (d *poolDequeue) unpack(ptrs uint64) (head, tail uint32) {
	const mask = 1<<dequeueBits - 1
	head = uint32((ptrs >> dequeueBits) & mask)
	tail = uint32(ptrs & mask)
	return
}

func (d *poolDequeue) pack(head, tail uint32) uint64 {
	const mask = 1<<dequeueBits - 1
	return (uint64(head) << dequeueBits) |
		uint64(tail&mask)
}

// pushHead在队列的头部添加val。如果
// 队列已满，则返回false。它只能由单个生产者调用。
func (d *poolDequeue) pushHead(val interface{}) bool {
	ptrs := atomic.LoadUint64(&d.headTail)
	head, tail := d.unpack(ptrs)
	if (tail+uint32(len(d.vals)))&(1<<dequeueBits-1) == head {
		// 队列已满。
		return false
	}
	slot := &d.vals[head&uint32(len(d.vals)-1)]

	// 检查头槽是否已被popTail释放。另一个goroutine仍在清理尾部，因此，队列实际上仍然满。头槽是空闲的，因此我们拥有它。增加头。这将槽的所有权传递给popTail 
	typ := atomic.LoadPointer(&slot.typ)
	if typ != nil {
		return false
	}

	if val == nil {
		val = dequeueNil(nil)
	}
	*(*interface{})(unsafe.Pointer(slot)) = val

	// 并起作用作为写入插槽的存储屏障。
	atomic.AddUint64(&d.headTail, 1<<dequeueBits)
	return true
}

// popHead删除并返回队列头部的元素。
// 如果队列为空，则返回false。它只能由单个生产者调用。
func (d *poolDequeue) popHead() (interface{}, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		head, tail := d.unpack(ptrs)
		if tail == head {
			// 队列为空。
			return nil, false
		}

		// 确认尾部和减量头。我们o这是在
		// 读取值以收回此
		// 插槽的所有权之前。
		head--
		ptrs2 := d.pack(head, tail)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
			// 我们成功收回插槽。
			slot = &d.vals[head&uint32(len(d.vals)-1)]
			break
		}
	}

	val := *(*interface{})(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
		val = nil
	}
	// 将插槽归零。与popTail不同，这不是与
	// pushHead竞争，因此在这里不需要小心。
	*slot = eface{}
	return val, true
}

// popTail删除了一个nd返回队列尾部的元素。
// 如果队列为空，则返回false。任何
// 用户数都可以调用它。
func (d *poolDequeue) popTail() (interface{}, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		head, tail := d.unpack(ptrs)
		if tail == head {
			// 队列为空。
			return nil, false
		}

		// 确认头和尾（用于上面的推测性检查
		// ）如果这成功了，那么我们拥有尾部的插槽。
		// 成功。
		ptrs2 := d.pack(head, tail+1)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
			slot = &d.vals[tail&uint32(len(d.vals)-1)]
			break
		}
	}

	// 我们现在拥有插槽。
	val := *(*interface{})(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
		val = nil
	}

	// 告诉pushHead我们已经完成了这个插槽。将
	// 插槽归零也很重要，这样我们就不会留下引用
	// 这一点无法使此对象的寿命超过所需时间。
	// 
	// 我们先向val写入，然后发布我们已完成
	// 通过原子方式写入typ来完成此插槽。
	slot.val = nil
	atomic.StorePointer(&slot.typ, nil)
	// 此时pushHead拥有该插槽。

	return val, true
}

// poolChain是poolDequ的动态大小版本eue.
// 
// 这是作为poolDequeues的双链表队列实现的，其中每个dequeue的大小是前一个的两倍。一次
// 出列已满，这将分配一个新的出列，并且只推送到
// 最新的出列。POP发生在列表的另一端，
// 一旦一个出列队列耗尽，它就会从列表中删除。
type poolChain struct {
	// head是要推送到的池出列。生产者只能访问
	// 因此不需要同步。
	head *poolChainElt

	// tail是要从中弹出tail的池出列。消费者可以访问
	// 所以读写必须是原子的。
	tail *poolChainElt
}

type poolChainElt struct {
	poolDequeue

	// 下一个和上一个链接到此
	// 池链中相邻的池链。
	// 
	// next由生产者以原子方式写入，由消费者以原子方式读取。它仅从nil转换为
	// 非nil。
	// 
	// prev由使用者以原子方式写入，由生产者以原子方式读取。它仅从
	// 非零转换为零。
	next, prev *poolChainElt
}

func storePoolChainElt(pp **poolChainElt, v *poolChainElt) {
	atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(pp)), unsafe.Pointer(v))
}

func loadPoolChainElt(pp **poolChainElt) *poolChainElt {
	return (*poolChainElt)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(pp))))
}

func (c *poolChain) pushHead(val interface{}) {
	d := c.head
	if d == nil {
		// 初始化链。
		const initSize = 8 // 必须是2的幂
		d = new(poolChainElt)
		d.vals = make([]eface, initSize)
		c.head = d
		storePoolChainElt(&c.tail, d)
	}

	if d.pushHead(val) {
		return
	}

	// 当前出列已满。分配一个两倍于
	// 大小的新值。
	newSize := len(d.vals) * 2
	if newSize >= dequeueLimit {
		// 不能再大了。
		newSize = dequeueLimit
	}

	d2 := &poolChainElt{prev: d}
	d2.vals = make([]eface, newSize)
	c.head = d2
	storePoolChainElt(&d.next, d2)
	d2.pushHead(val)
}

func (c *poolChain) popHead() (interface{}, bool) {
	d := c.head
	for d != nil {
		if val, ok := d.popHead(); ok {
			return val, ok
		}
		// 上一次出列中可能仍有未使用的元素，请尝试备份。
		d = loadPoolChainElt(&d.prev)
	}
	return nil, false
}

func (c *poolChain) popTail() (interface{}, bool) {
	d := loadPoolChainElt(&c.tail)
	if d == nil {
		return nil, false
	}

	for {
		// 在*弹出尾部之前加载下一个指针
		// /*非常重要。一般来说，d可能是
		// 暂时为空，但如果在
		// pop之前next为非零且pop失败，则d永久为
		// 空，这是
		// 安全从链中删除d的唯一条件。
		d2 := loadPoolChainElt(&d.next)

		if val, ok := d.popTail(); ok {
			return val, ok
		}

		if d2 == nil {
			// 这是唯一的出列。现在是空的，但将来可能会被推到。
			return nil, false
		}

		// 链的尾部已排空，因此继续
		// 到下一个出列。尝试将其从链
		// 中删除，以便下一次弹出不必再次查看空的
		// 出列。我们赢得了比赛。清除上一个指针，这样垃圾收集器可以收集空的
		if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.tail)), unsafe.Pointer(d), unsafe.Pointer(d2)) {
			// 出列，这样popHead就不会备份
			// 超出需要的部分。
			storePoolChainElt(&d2.prev, nil)
		}
		d = d2
	}
}
